package jianzhioffer;



public class ReverseList {


    // 双指针
    public ListNode reverseList(ListNode head) {
        ListNode p = head;
        ListNode q = null;
        while (p!=null){
            ListNode t = p.next;
            p.next = q;
            q = p;
            p = t;
        }
        return q;
    }

    // 递归

    public ListNode reverseList2(ListNode head) {
        // 出口是只有一个或者没有结点的时候。
        if (head==null|| head.next==null){
            return head;
        }

       ListNode node =  reverseList2(head.next);
        // 将最后一个结点的指针指向head
        head.next.next = head;
        head.next = null;
        return node;
    }
}
